不学肯定是不行的，比赛果然考了
经典问题
给一颗有根树，每个节点有一个颜色，多次询问节点$u$的子树中颜色$v$的数量。
$(n,q\le10^5)$
题解
- 肯定要离线处理
- 首先暴力的方法可以每次暴力统计每个节点子树的颜色，对询问回答即可
- 显然这样暴力的时间复杂度是$O(n^2)$
- 考虑优化我们可以每次最后遍历重儿子，可以这样做的原因是：因为最后遍历重儿子，重儿子不影响其兄弟节点的询问。
- 这样的复杂度是$0(n\log n)$，因为每次合并，被合并的节点的集合至少是原来集合的两倍，这样最多只能合并$\log n$次。
算法步骤
- 预处理出dfs序和每个节点的重儿子
- dfs优先处理轻儿子，再处理重儿子、
- 统计数量，对询问回答
- 删除轻儿子的影响，保留重儿子的影响。
总结
树上启发式合并主要利用了每次合并的集合至少都是被合并进来的集合的规模的两倍，因此可以保证至多只会合并$\log$次数，减少了大量的重复统计。